package com.leetcode.study.interview;

import java.util.Objects;

public class KMPTest {

    public static void main(String[] args) {


        String a = "abcadced";
        String b = "adc";

        System.out.println(kmpSearch(a, b));

    }

    /**
     * 朴素算法，就是遍历字符串s和字符串p，当比到相同的字符串，i指针（字符串s）和j指针（字符串p）向后+1,
     * 否则i回到上一个位置的前一个位置，即 i= i-j + 2；j=1 回到第一个字符，重新比较
     * @param s
     * @param p
     * @return
     */
    public static String simpleSearch(String s, String p) {
        int po = -1;

        // 定义两个指针，i为s串下标指针
        // j为p串下标指针
        int i = 0, j = 0;
        while (i < s.length() && j < p.length()) {
            char s0 = s.charAt(i);
            System.out.println(">>>>>>>>>> " + s0);
            char p0 = p.charAt(j);
            System.out.println(">>>>>>>>>> " + p0);

            if (Objects.equals(s0, p0)) {
                i++;
                j++;
            }
            else {
                i= i-j + 1;
                j = 0;
            }
        }

        // j最多到p.length()就停了 ，指针j和其相同时，说完全匹配了，j已经走到了全部字符串的后一个指针位置
        if (j == p.length()) {
            // 在字符串
            po = i - p.length();
        }


        if (po == -1) {
            return null;
        }
        return s.substring(po, po + p.length());
    }



    public static String kmpSearch(String s, String p) {
        int po = -1;

        int[] next = getNext(p);

        // 定义两个指针，i为s串下标指针
        // j为p串下标指针
        int i = 0, j = 0;
        while (i < s.length() && j < p.length()) {
            char s0 = s.charAt(i);
            System.out.println(">>>>>>>>>> " + s0);
            char p0 = p.charAt(j);
            System.out.println(">>>>>>>>>> " + p0);

            if (j == 0 || Objects.equals(s0, p0)) {
                i++;
                j++;
            }
            else {
                j = next[j];
            }
        }

        // j最多到p.length()就停了 ，指针j和其相同时，说完全匹配了，j已经走到了全部字符串的后一个指针位置
        if (j == p.length()) {
            // 在字符串
            po = i - p.length();
        }

        if (po == -1) {
            return null;
        }
        return s.substring(po, po + p.length());
    }


    /**
     * 获取模式串的next数组
     * @param s
     * @return
     */
    public static int[] getNext(String s) {
        int[] next = new int[s.length()+1];
        int i = 1;
        int j = 0;


        next[1] = 0;

        // 其实next[2] = 1
        while (i < s.length()) {

            // 处理next[2] = 1 或者 每次都比较，都是相同的字符
            // 指针向后移动
            if (j == 0 || Objects.equals(s.charAt(i), s.charAt(j))) {

                ++i;
                ++j;
                next[i] = j;




            }
            else {
                j = next[j];

            }
        }

        return next;

    }


}
